Approach #1: Heap [Accepted]

Intuition and Algorithm

Let's keep a priority queue of which square we can walk in next. We always walk in the smallest one that is 4-directionally adjacent to ones we've visited.

When we reach the target, the largest number we've visited so far is the answer.

Complexity Analysis

• Time Complexity: $O(N^2 \log N)$. We may expand $O(N^2)$ nodes, and each one requires $O(\log N)$ time to perform the heap operations.

• Space Complexity: $O(N^2)$, the maximum size of the heap.

Approach #2: Binary Search and DFS [Accepted]

Intuition and Algorithm

Whether the swim is possible is a monotone function with respect to time, so we can binary search this function for the correct time: the smallest T for which the swim is possible.

Say we guess that the correct time is T. To check whether it is possible, we perform a simple depth-first search where we can only walk in squares that are at most T.

Complexity Analysis

• Time Complexity: $O(N^2 \log N)$. Our depth-first search during a call to possible is $O(N^2)$, and we make up to $O(\log N)$ of them.

• Space Complexity: $O(N^2)$, the maximum size of the stack.

Approach #3: Minimal Spanning Tree Algorithm (Union-Find)

Intuition

One can formulate the problem as building a minimum spanning tree, i.e. find minimum edges to connect all nodes in a graph.

In our case, we would like to find the fastest path (i.e. minimal waiting time) to reach from the top-left point to the bottom-right point of the grid.

Rather than finding the spanning tree to connect all cells in the grid, we are only interested to find the spanning that connect our starting and ending points.

One of the well-known algorithms for the minimal spanning tree problem is called Kruskal's algorithm, proposed by Joseph Kruskal in 1956.

So the idea of this solution is to adapt the Kruskal's algorithm to solve our problem here.

Algorithm

The essence of the Kruskal's algorithm relies on the disjoint-set data structure, also known as union-find data structure, which tracks a set of elements partitioned into a number of disjoint (non-overlapping) subsets.

The Kruskal's algorithm starts from a list of sets, where each set contains only a single node, it then greedily merges the sets together until there is only one set left i.e. the minimal spanning tree.

Essentially, the algorithm can be implemented with two major functions: union(a, b) and find(a). With the union(a, b) function, we merge two sets together. And with the find(a) function, we find the representative (also known as parent) of the set.

Here are some overall steps of an adapted Kruskal's algorithm:

• We consider each cell in the grid as a node in a graph, and the value in the cell represents its weight.

• We then sort the cells based on their weights, in the ascending order.

• We then iterate through the sorted cells.

  • At each iteration, we add the neighbor cells around the current cell to the spanning tree.

  • At any moment, if we find that the starting and ending points are connected thanks to the newly added nodes, we exit the loop. And the weight of the current cell would be the minimal waiting time, before we complete the spanning tree.

Here is the solution proposed by leet212. Also, many users have proposed similar ideas and solutions in the discussion forum.

Complexity Analysis

Let $N$ be the width of the grid (N*N).

• Time Complexity: $O(N^2 \log N^2)$.

  • First of all, we have in total $N^2$ cells in the grid.

  • Since we sort cells based on their weights, it would take $\mathcal{O}(N^2 \log N^2)$ time for this sorting operation.

  • We iterate through the cells, i.e. $N^2$ steps. At each step, the union() function requires $\mathcal{O}(\log^{*} N^2)$ complexity, which one can refer to the proof for more details.

  • To sum up, the overall time complexity of the algorithm is $\mathcal{O}(N^2 \log N^2) + \mathcal{O}(N^2 \log^{*} N^2) = \mathcal{O}(N^2 \log N^2)$.

• Space Complexity: $O(N^2)$. We use some auxiliary data structures that are proportional to the size of the grid, i.e. $N^2$.